import sun.plugin.javascript.navig.Link;

import java.util.*;

/**
 * @author VernHe
 * @date 2021年04月22日 10:56
 */
public class Solution_040 {
    public static void main(String[] args) {
        Solution_040 solution = new Solution_040();
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println(res);
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();

        // 顺序剪枝，要进行排序
        Arrays.sort(candidates);
        select(candidates, target, 0, path, result, 1);
        return result;
    }

    /**
     * 进行选择
     *
     * @param candidates 候选数组
     * @param target     当前层的target
     * @param begin      当前层开始查找的位置
     * @param path       到达当前位置的路径
     * @param result     结果
     */
    private void select(int[] candidates, int target, int begin, Deque<Integer> path, List<List<Integer>> result, int level) {
        // 递归基
        if (target == 0) {
            // 保存路径
            result.add(new ArrayList<>(path));
            return;
        }

        // 在候选数组中进行查找
        for (int i = begin; i < candidates.length; i++) {
            if (i > begin && candidates[i] == candidates[i - 1]) {
                System.out.println(candidates[i] + "---" + candidates[i - 1] + "与前一个相等，不跳出循环，而是继续选择下一个");
                // 与前一个相等，如果与前两个相等就不限制
                continue;
            }

            if (target - candidates[i] < 0) {
                System.out.println("target = " + target + ", current = " + candidates[i] + ",不能选择该数，跳出循环");
                break;
            }

            // 如果可以选择
            path.addLast(candidates[i]);
            System.out.println("选择了index为" + i + "的【" + candidates[i] + "】，path: " + path);
            // 继续往后找
            select(candidates, target - candidates[i], i + 1, path, result, level + 1);
            // 【回溯】
            path.removeLast();
            System.out.println("删除了index为" + i + "的【" + candidates[i] + "】，path: " + path);
        }
    }
}
